The detection of the received signal in a data communication system is challenging due to several factors. These factors include, but not limited to, noise, cross-talk, and Inter-Symbol Interference (ISI).
ISI, as its name indicates, is the interference caused by the transmission of one symbole to other symbols in the transmitted sequence. FIG. 1 illustrates a typical bandwidth-limited channel pulse response 100. Pulse response 100 shows a power dispersion (vertical) over time (horizontal axis 104). The peak 109 of the response 100 is considered to be indicative of the symbol transmitted. Symbol 109 will overlap with the symbols sent before and after it. Those skilled in the art will appreciate that it is not possible to abruptly terminate the power of a symbol without unwanted effects. Symbol 109 will contribute to interference with the subsequent symbol and the magnitude of this interference is illustrated by point 110 on the response curve. Symbol 109 will also interfere with the previously transmitted symbol and the magnitude of this interference is illustrated by point 120. Points 112 and 114 illustrate the interference with the second and third symbols transmitted after symbol 109, while point 122 indicates the interference contributed by pulse response 100 to the symbol transmitted two slots before pulse response 100. This figure illustrates the concept of signal dispersion in both the negative direction 106 and the positive direction 108. While this is a common ISI pattern for a channel pulse response, some channels may exhibit different ISI patterns.
Several methods to address ISI are known or suggested in the art. For example Decision Feedback Equalization (DFE), Feed Forward Equalization (FFE), and Maximum Likelihood Sequence Detection (MLSD) are commonly used to mitigate ISI in a variety of transmission environments. It will be understood that the above described ISI is simply one of a number of sources of noise in real world transmission channels. The choice of the proper detection scheme depends on many parameters, including the complexity of implementation of the detector. A combination of different detection techniques can also be employed.
Although MLSD results in a superior performance over DFE and FFE, it is considered to have a higher level of implementation complexity.
A further known technique, Reduced-State Sequence Detection (RSSD), is a variant of MLSD that sacrifices some of the performance of MLSD for a lower level of implementation complexity while still exhibiting superior performance relative to DFE and FFE. Decision Feedback Equalization (DFE) operates based on two assumptions: first, that the channel pulse response is known, or can be estimated by the receiver; and second, that prior to detection of any current symbol, the DFE successfully detected the previous symbols. With this information, the DFE process can proceed with detecting the current symbol by compensating for interference caused by the previous symbol or symbols. This interference from previous symbols is designated “post-cursor ISI” and it corresponds to the dispersion values 120,122, and so on from FIG. 1.
However, DFE is unable to remove the interference terms from the symbols that are transmitted after the symbol under detection, designated “pre-cursor ISI”, which corresponds to the dispersion values 110,112,114, and so on from FIG. 1.
DFE implementations often use a slicer to obtain an initial estimate of symbol values from received samples based on comparison of the ISI-corrected sample to one or more threshold values. The slicer slices at these thresholds, binning the samples into one or more bins corresponding to one or more symbol values. Assuming that the estimated symbol values at the output of the DFE slicer correctly represent the transmitted symbols, the estimated symbols can be employed to construct a replica of the post-cursor ISI terms that the transmitted symbols corresponding to the estimated symbols had added to the current symbol. This is where the knowledge of channel pulse response is needed to apply the corresponding weights (calculated from the pre- and post-cursor dispersion levels from FIG. 1) to calculate different ISI terms. This estimated post-cursor ISI contribution can then be removed (i.e., subtracted) from the received signal to yield the current transmitted symbol. FIG. 2 illustrates this DFE operation, showing how a DFE loop 200 outputs estimated symbols 202 based on received samples 204. The DFE loop 200 first subtracts the sum of total calculated ISI 206 from N previous symbols from the received sample 204. The DFE loop 200 then passes the result through a slicer 208. The estimated current symbol 202 is provided as feedback to the loop 200 via a one-symbol delay node 210. This delayed symbol value represents the 1st previous symbol 212, and it passes through a chain of (N−1) additional one-symbol delay nodes 210 to create a chain of each of the 2nd previous symbol 214 through Nth previous symbol 216. Each such previous symbol 212,214, . . . 216 is weighted by a weight 222,224, . . . 226 corresponding to the magnitude of dispersion from that previous symbol into the current symbol (i.e. values 120,122 and so on from FIG. 1). By multiplying those weights 222,224, . . . 226 by the previous symbol values 212, 214, . . . 216, ISI values 232,234, . . . 236 are calculated for each previous term. The ISI values 232,234, . . . 236 are summed to produce the total ISI 206.
DFE may not perform optimally for at least two reasons. First, it removes, hence ignores, the ISI components of the received signal that contain information about the stream of transmitted symbols (e.g., DFE loop 200 from FIG. 2 outputs an estimated symbol 202 that has had all calculated ISI terms 206 removed from it, making that information 206 unavailable to the system for use in further error-correction). Second, its reliance on feedback based on its previous decisions (e.g. estimated symbol 202 from FIG. 2 is fed back to loop 200) may result in error propagation, wherein the DFE makes even more errors if its previous decisions are faulty.
Feed Forward Equalization (FFE) operates differently, and is able to cancel both pre-cursor and post-cursor ISI. The basic operation of an FFE detector is based on two requirements. First, as with DFE, it assumes that the channel pulse response is known, or can be estimated by the receiver. Second, FFE processes the symbols after a delay so that the received symbol within that delay represent symbols that have been transmitted after the symbol under process—this delay enables FFE to handle pre-cursor ISI in addition to post-cursor ISI. Using this information, the FFE can proceed with detecting the current symbol (i.e. the symbol under process) by removing the interference terms from the previous as well as the next symbols that add ISI to the current symbol during transmission.
By passing the received signal through a chain of delay cells and deciding on the point along this chain that represents the symbol under detection, the FFE can calculate the ISI terms that were caused by the previous symbols as well as the next symbols. This is where the knowledge of channel pulse response is needed, to apply the corresponding weights to calculate different ISI terms. The total ISI replica can then be removed (i.e. subtracted) from the received signal to yield the current transmitted symbol. FIG. 3 illustrates this FFE operation, showing how an FFE system 300 uses a pre-cursor ISI error-correction loop 302 and a post-cursor ISI error-correction loop 304 to remove pre-cursor ISI 306 from P next symbols and post-cursor ISI 308 from N previous symbols, respectively, to generate an ISI-free sample 310 by subtracting the pre-cursor ISI 306 and post-cursor ISI 308 from the current sample 312. The current sample 312 is the result of a P-long chain of one-symbol delay nodes 314 applied to the received samples 316. The received samples 316 and each incrementally delayed sample 318 . . . 320 in this chain correspond to the Pth next symbol 316 through 1st next symbol 320 relative to the current sample 312. Each of these symbols 316 . . . 320 has a weight 322 . . . 324 applied to it, much like in the sample DFE loop 200, but here the weights 322 . . . 324 correspond to the pre-cursor dispersion values 110,112,114, and so on from FIG. 1. As in DFE loop 200, these weighted ISI values 326 . . . 328 derived from the Pth next symbol 316 through 1st next symbol 320 are summed to produce the total pre-cursor ISI 306.
The current sample 312 has a further N-long chain of one-symbol delay nodes 314 applied to it to generate the 1st previous symbol 330 through Nth previous symbol 332 relative to the current sample 312. These symbols 330 . . . 332 are weighted to calculate ISI terms 334 . . . 336, which are then summed in much the same way as a DFE loop such as DFE loop 200 to produce the total post-cursor ISI 308.
The ISI-free sample 310 (or ISI-compensated sample, the terms will be understood by those skilled in the art as being used somewhat interchangeably) is processed by a slicer 340 to produce an estimated symbol 350. Notably, this estimated symbol 350 is not used to provide feedback to the FFE system 300, unlike with the example DFE loop 200.
FFE may not perform optimally for at least two reasons. First, like DFE, it removes, hence ignores, the ISI components of the received signal that contain information about the stream of transmitted symbols. Second, FFE may result in noise enhancement, since contrary to DFE which uses noise-free sliced symbols (e.g. estimated symbols 202) to remove their ISI terms (e.g. estimated symbols 202 are fed back to DFE loop 200), FFE uses delayed versions of the received signal prior to slicing them. Any noise present in the received signal may thus contribute to the overall noise, hence enhance it when weighted versions of that signal are summed (such as the summation of values 326 . . . 328 and values 334 . . . 336, each of which is derived by weighting a delayed version of the potentially noisy received signal 316).
Maximum Likelihood Sequence Detection (MLSD) provides a third method of ISI detection/cancellation as an alternative to (or in addition to) DFE and FFE. The basic operation of an MLSD detector is based on the fact that ISI terms convey useful information and can therefore be included in the detection process to improve detector performance. This is in contrast with DFE and FFE, which calculate ISI terms in order to remove them from the received signal.
By including the interaction between different symbols in the detection process, the received symbols can be processed as a sequence rather than as individual symbols. This introduces the concept of “sequence detection”.
However, inclusion of the entire signal (or the inclusion of all the samples representing the signal) is often impractical and could involve infinite latency and complexity in the detection process. As a result, the MLSD system operates on a sequence of samples from the signal of predetermined length, with this length being based on a trade-off between the truncation penalty and various practical considerations.
Importantly, in addition to ISI, the received signal is also contaminated by noise. Thus, the problem of sequence detection becomes the choice of a particular sequence among all possible sequences that best resembles the transmitted sequence in the presence of this combination of interference (ISI) and noise. This choice of a particularly likely sequence of symbols is what “maximum likelihood sequence detection” refers to.
FIG. 4 illustrates an example of maximum likelihood sequence detection (MLSD) from among possible sequences that start from equivalent initial conditions. On the left is a table 402 showing all possible permutations of a sequence three symbols in length in an encoding scheme having three symbol values (A, B, and C). The highlighted row shows an example sequence permutation 404: “C C A”. This sequence is used in the following example of MLSD as the actual transmitted sequence being detected via the MLSD technique.
On the right in FIG. 4 is a graph 410 showing all possible transitions between consecutive symbols in such a length-3 sequence. Each such transition has an associated “cost”: a penalty associated with that transition. This cost penalty, also called a “branch metric”, is calculated by a technique outlined in detail below: in general terms, the magnitude of the cost penalty is inversely proportional to the likelihood of that transition actually having transpired at that point in the transmitted signal based on the closeness of the received signal to the expected value associated with that transition. In the illustrated example, the transition 412 from upper left node “A” 414 to upper middle node “A” 415 has a branch metric, or cost penalty, of 1. The transition 416 from lower middle node “C” 418 to middle right node “B” 420 has an associated cost penalty of 7. The graph 410 denotes example cost penalties/branch metrics for each of the transitions.
To calculate the most likely transmitted sequence based on a received signal, an MLSD system begins by setting the initial cost at the start of all sequences (on the far left side) to zero. Moving from left to right in graph 410, each subsequent node in the graph (such as node 418) is given a minimum accumulated cost equal to the lowest branch metric of all the transitions leading to it (in this case transitions 422, 424, and 426 from left-side nodes “A”, “B”, and “C” respectively). In the case of node 418, the minimum accumulated cost is zero, corresponding to the minimum of the branch metrics of each of transitions 422 (branch metric=4), 424 (branch metric=3), and 426 (branch metric=0).
The “winner” (i.e. the most likely transmitted sequence as determined by the MLSD) corresponds to the path through the graph 410 that has, in total, the lowest minimum accumulated cost. In this case, that detected “winner” sequence is “C C A”, due to the lowest minimum accumulated cost.
The minimum accumulated cost for each symbol at each time step is shown in the graph 410 with arrows 428 pointing to the node where they came from. The lowest cost path leading to each symbol at each time step is shown in either bold lines 430 or dashed bold lines 432 in the graph 410. The final lowest cost path that results in the lowest cost at the end of the sequence is shown by the solid bold lines 430. The dashed bold lines 432 indicate the temporary optimum paths that lost the competition.
As shown in FIG. 4, an MLSD detector tries to find the path with the lowest accumulated cost among all possible paths that pass through different nodes of the graph through the allowed transitions that are labeled by their corresponding transition cost penalties.
Throughout this specification, and particularly in the context of MLSD, familiar terms used in data communications may be used interchangeably with the following more generic terms: “path” and “sequence”; “accumulated cost” and “state metric”; “node” and “state”; “graph” and “trellis”; “transition” and “branch”; and “transition cost” (or “cost” or “cost penalty”) and “branch metric”.
Branch metrics used in MLSD may be calculated by using a cost penalty criterion, such as absolute or mean square, to the difference (error) between an expected value and a measured value of a received signal at a given time. The expected value may be calculated with reference to a known or estimated transfer function of a communication medium.
An MLSD detector may be implemented by an application of the Viterbi Algorithm, which is known in the art and described in detail by G. D. Forney, Jr. in “The Viterbi Algorithm,” Proc. of the IEEE, Vol. 61, No. 3, pp. 268-278, March 1973.
An MLSD receiver seeking to maximize the accuracy of the sequence detection process would wait until the entire transmitted sequence is received before deciding on the most-likely sequence. However, to minimize the detection latency, this waiting period can be shortened at the price of some performance penalty. The trade-off between the latency and performance degradation depends on several factors including the structure of the trellis diagram and practical limitations. A general rule of thumb is to wait several symbol times equal to at least 4 to 6 times the number of states of the trellis before applying the MLSD to detect a sequence of symbols. Thus, when receiving a 4-PAM signal with four symbol values, an MLSD should wait to receive 16 to 24 symbol intervals of the signal before applying the MLSD process to identify most likely states (i.e. the states with minimum accumulated costs). The decision waiting time is called the path memory depth, and is stated in terms of the number of symbol intervals. It is important to note that this delay does not apply to processing the signal. Branch metric, state metric, and updating the content of the path memory with the latest survivor trace-back continue to happen sequentially and continually at every signal interval. Only the final decision-making step of the MLSD process (i.e. identifying the states having minimum accumulated cost) is delayed.
This delay ensures that enough information of the signal has been processed. The delay gives the detector enough time so that the surviving path memories are likely to merge: i.e., a backwards traverse of the trellis tends to result in paths of least accumulated cost converging at the same node and thereafter (traversing backwards) being identical. This reduces the number of paths that need to be calculated for the remainder of the backwards traverse starting at the node where the convergence occurs. For example, suppose that a backwards traverse of a trellis results in the determination that the path with lowest accumulated cost passing through node “A” at time t is a path that also passes through node “A” at t−1. It also results in the determination that the path with lowest accumulated cost passing through node “B” at time t is a path that also passes through node “A” at t−1. In that case, the two paths will be identical traversing backwards from node “A” at time t−1, and will only need to be calculated once (i.e. as a single, converged path).
If this symbol decision process repeats at every symbol interval at a speed equal to the signal transmission speed, the detector output will have a latency equal to the path memory depth.
MLSD has the potential to achieve highly accurate sequence detection, but as the modulation scheme increases the number of symbol values above 2-PAM (binary), or the number of ISI terms increases beyond 2, the number of combinations to be calculated at each unit interval of time increases exponentially. A potentially less complex alternative to MLSD is Reduced-State Sequence Detection (RSSD). This technique is described in detail by M. V. Eyuboglu and S. U. Qureshi in “Reduced-State Sequence Estimation with Set Partitioning and Decision Feedback,” IEEE Trans. On Communications, Vol. 36, No. 1, pp. 13-20, January 1988. RSSD reduces the number of states used in sequence detector, thereby reducing the number of calculations required under the Viterbi Algorithm during each unit interval (UI) of the received signal. However, this reduction in calculation complexity introduces ambiguity that must be resolved through other means.
In RSSD, selected states of the trellis diagram of the MLSD are partitioned into new states (sometimes called “hyper-states”) to convert the trellis diagram into a trellis diagram with fewer number of states, hence fewer state metrics to be calculated. As a result of this state partitioning, the branches that fall inside the same partition (i.e., both start and end states belong to the same partition) will have to merge to a single branch. Each branch could represent either a transition caused by a different symbol or a different memory trace-back, or both. Accordingly, the ambiguities resulting from state partitioning have to be resolved at some point in order to ultimately achieve proper detection.
The general solution to the resolution of these ambiguities is to employ a feedback mechanism that works in conjunction with the RSSD detector. This feedback mechanism essentially behaves like a DFE detector that, along with the RSSD detector, can complete the task of detection. An example of such a hybrid structure is illustrated in FIG. 5(A) and FIG. 5(B).
FIG. 5(A) shows an F-state MLSD sequence detector trellis 502 used to generate estimated symbols 506 based on received samples 504. This F-state detector trellis 502 illustrates a full-state sequence detector, i.e. as an MLSD.
FIG. 5(B) shows a hybrid Reduced-State Sequence Detector (RSSD) system 510 comprising an R-state sequence detector 512 and a decision feedback loop 514. In this example, R<F, showing that RSSD can accomplish detection using a reduced number of states relative to the full F-state MLSD implementation 502. Like an MLSD, the RSSD 510 also generates estimated symbols 516 based on received samples 518.
The R-state sequence detector 512 provides estimated symbols 520 as feedback to the loop 514. This estimated symbol set 520 is fed through a delay chain 522; the delayed symbol set 524 is then weighted by a weight vector 525 similar to what was described in the DFE example above to produce a quantity 526 to be subtracted from the received samples 504 similar to the DFE example above. FIG. 5(B) and the above explanation demonstrate the resemblance of the RSSD feedback loop to that of a regular DFE.
The combination of the reduced-stated sequence detector (e.g. R-state detector 512) and the decision feedback loop connected to it (e.g. feedback loop 514) behaves like a hybrid detector performing somewhere between the performance lines of a full state MLSD and a regular DFE. For this reason, the resulting RSSD is sometimes called a Decision Feedback Sequence Detector (DFSD) or equivalently, a Decision Feedback Sequence Estimator (DFSE). The degree to which the performance is closer to each end of the spectrum of MLSD to DFE depends on the extent of state partitioning. If a greater number of states are placed in one partition, more deviation from the full state MLSD results, and the performance becomes closer to the performance of a DFE. The extreme case of partitioning all the states of an MLSD into one single group converts the MLSD into a regular DFE, as shown by the present inventor, M. H. Shakiba, in “Analog Viterbi Detection for Partial-Response Signaling,” Ph.D. Dissertation, Department of Electrical and Computer Engineering, University of Toronto, 1997 (hereinafter the “Shakiba Dissertation”), which is hereby incorporated by reference in its entirety.
Due to implementation complexity challenges, sequence detection (MLSD or even RSSD) has not historically been widely used in high-speed data communication systems (such as data communication over backplanes). Given the ever-increasing need for higher data rates while achieving the performance requirements of the system, there exists a need for sequence detection systems having reduced complexity relative to known MLSD and RSSD techniques for use in high speed data communication applications.